#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 函数声明
bool isSafeState(vector<vector<int>> &Allocation, vector<vector<int>> &Need, vector<int> &Available, vector<int> &SafeSequence);
bool requestResources(int processID, vector<int> &Request, vector<vector<int>> &Allocation, vector<vector<int>> &Need, vector<int> &Available, vector<int> &SafeSequence);

// 全局变量声明
int pnumber, renumber;

int main()
{
    cout << "Enter number of processes: ";
    cin >> pnumber;
    cout << "Enter number of resources: ";
    cin >> renumber;

    vector<int> Available(renumber);
    vector<vector<int>> Max(pnumber, vector<int>(renumber));
    vector<vector<int>> Allocation(pnumber, vector<int>(renumber));
    vector<vector<int>> Need(pnumber, vector<int>(renumber));

    cout << "Enter Available resources: ";
    for (int i = 0; i < renumber; i++)
    {
        cin >> Available[i];
    }

    cout << "Enter Max matrix: " << endl;
    for (int i = 0; i < pnumber; i++)
    {
        for (int j = 0; j < renumber; j++)
        {
            cin >> Max[i][j];
            Need[i][j] = Max[i][j]; // 初始化Need矩阵
        }
    }

    cout << "Enter Allocation matrix: " << endl;
    for (int i = 0; i < pnumber; i++)
    {
        for (int j = 0; j < renumber; j++)
        {
            cin >> Allocation[i][j];
            Need[i][j] -= Allocation[i][j]; // 计算Need矩阵
            Available[j] -= Allocation[i][j];
        }
    }

    vector<int> SafeSequence(pnumber);

    // 打印初始状态
    cout << "Initial State:" << endl;
    cout << "Available: ";
    for (int i = 0; i < renumber; i++)
    {
        cout << Available[i] << " ";
    }
    cout << endl;

    cout << "Allocation:" << endl;
    for (int i = 0; i < pnumber; i++)
    {
        for (int j = 0; j < renumber; j++)
        {
            cout << Allocation[i][j] << " ";
        }
        cout << endl;
    }

    cout << "Need:" << endl;
    for (int i = 0; i < pnumber; i++)
    {
        for (int j = 0; j < renumber; j++)
        {
            cout << Need[i][j] << " ";
        }
        cout << endl;
    }

    // 检查初始状态是否安全并输出安全序列
    if (isSafeState(Allocation, Need, Available, SafeSequence))
    {
        cout << "Initial state is safe. Safe Sequence: ";
        for (int i = 0; i < pnumber; i++)
        {
            cout << "P" << SafeSequence[i] << " ";
        }
        cout << endl;
    }
    else
    {
        cout << "Initial state is not safe." << endl;
    }

    while (true)
    {
        int processID;
        vector<int> Request(renumber);

        cout << "Enter process ID and its resource request: ";
        cin >> processID;
        for (int i = 0; i < renumber; i++)
        {
            cin >> Request[i];
        }

        if (requestResources(processID, Request, Allocation, Need, Available, SafeSequence))
        {
            cout << "Request granted." << endl;

            cout << "Available: ";
            for (int i = 0; i < renumber; i++)
            {
                cout << Available[i] << " ";
            }
            cout << endl;

            cout << "Allocation:" << endl;
            for (int i = 0; i < pnumber; i++)
            {
                for (int j = 0; j < renumber; j++)
                {
                    cout << Allocation[i][j] << " ";
                }
                cout << endl;
            }

            cout << "Need:" << endl;
            for (int i = 0; i < pnumber; i++)
            {
                for (int j = 0; j < renumber; j++)
                {
                    cout << Need[i][j] << " ";
                }
                cout << endl;
            }

            cout << "Safe Sequence: ";
            for (int i = 0; i < pnumber; i++)
            {
                cout << "P" << SafeSequence[i] << " ";
            }
            cout << endl;
        }
        else
        {
            cout << "Request denied. System would be in unsafe state." << endl;
        }

        char continueRequest;
        cout << "Do you want to make another request? (y/n): ";
        cin >> continueRequest;
        if (continueRequest != 'y' || continueRequest != 'Y')
        {
            break;
        }
    }

    return 0;
}

bool requestResources(int processID, vector<int> &Request, vector<vector<int>> &Allocation, vector<vector<int>> &Need, vector<int> &Available, vector<int> &SafeSequence)
{
    for (int i = 0; i < renumber; i++)
    {
        if (Request[i] > Need[processID][i])
        {
            cout << "Error: Process has exceeded its maximum claim." << endl;
            return false;
        }
        if (Request[i] > Available[i])
        {
            cout << "Error: Resources not available." << endl;
            return false;
        }
    }

    for (int i = 0; i < renumber; i++)
    {
        Available[i] -= Request[i];
        Allocation[processID][i] += Request[i];
        Need[processID][i] -= Request[i];
    }

    if (isSafeState(Allocation, Need, Available, SafeSequence))
    {
        return true;
    }
    else
    {
        for (int i = 0; i < renumber; i++)
        {
            Available[i] += Request[i];
            Allocation[processID][i] -= Request[i];
            Need[processID][i] += Request[i];
        }
        return false;
    }
}

bool isSafeState(vector<vector<int>> &Allocation, vector<vector<int>> &Need, vector<int> &Available, vector<int> &SafeSequence)
{
    vector<int> Work = Available;
    vector<bool> Finish(pnumber, false);

    int count = 0;
    while (count < pnumber)
    {
        bool found = false;
        for (int i = 0; i < pnumber; i++)
        {
            if (!Finish[i])
            {
                int j;
                for (j = 0; j < renumber; j++)
                {
                    if (Need[i][j] > Work[j])
                    {
                        break;
                    }
                }
                if (j == renumber)
                {
                    for (int k = 0; k < renumber; k++)
                    {
                        Work[k] += Allocation[i][k];
                    }
                    SafeSequence[count++] = i;
                    Finish[i] = true;
                    found = true;
                }
            }
        }
        if (!found)
        {
            return false;
        }
    }
    return true;
}
